import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Imp implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}

public class Test {

    public static int[] smallestK(int[] array, int k){
        int[] ret = new int[k];
        if(array == null || k == 0){
            return ret;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Imp());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(array[i]);
        }
        for (int i=k;i < array.length;i++){
            int top = priorityQueue.peek();
            if (array[i] < top){
                priorityQueue.poll();
                priorityQueue.offer(array[i]);
            }
        }

        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        return ret;
    }

    public static void main(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {12,23,45,56,78,89,98,74,65,32};
        testHeap.initElem(array);
        testHeap.createHeap();
        testHeap.heapSort();
        System.out.println("===");
    }

    public static void main4(String[] args) {
        int[] array = {1,3,15,7,19,10};
        int[] ret = smallestK(array,3);
        System.out.println(Arrays.toString(ret));
    }

    public static void main3(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int[] array = {1,3,15,7,19,10};
        //相当于以向上调整的方式 建立小根堆
        for (int i = 0; i < array.length; i++) {
            priorityQueue.offer(array[i]);
        }
        int k =3;
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = priorityQueue.poll();
        }
        System.out.println(Arrays.toString(ret));
    }

    public static void main2(String[] args) {
        Imp imp = new Imp();
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(imp);
        priorityQueue.offer(10);
        priorityQueue.offer(5);
        priorityQueue.offer(6);

        System.out.println(priorityQueue.poll());
        System.out.println(priorityQueue.poll());
    }
    public static void main1(String[] args) {
        TestHeap testHeap = new TestHeap();
        int[] array = {12,23,45,56,78,89,98,74,65,32};
        testHeap.initElem(array);

        testHeap.createHeap();

        testHeap.push(80);
        System.out.println("==");
    }
}
